package 二分查找;
import java.util.*;
/**
 * 该类用于在二维矩阵中查找目标值。
 * 时间复杂度：O(m + n)，空间复杂度：O(1)
 */
public class searchMatrix2 {
    /**
     * 在二维矩阵中查找目标值。
     * 该方法从矩阵的右上角开始，根据目标值与当前元素的大小关系移动指针。
     * @param matrix 二维矩阵
     * @param target 目标值
     * @return 如果目标值存在于矩阵中，则返回 true，否则返回 false
     */
    public boolean searchMat(int[][] matrix, int target) {
        int left = matrix[0].length - 1; // 从右上角开始
        int right = 0; // 从第一行开始
        while(left >= 0 && right < matrix.length) { // 当指针在矩阵范围内时继续循环
            if(matrix[right][left] < target) right++; // 如果当前元素小于目标值，向下移动
            else if(matrix[right][left] > target) left--; // 如果当前元素大于目标值，向左移动
            else return true; // 如果找到目标值，返回 true
        }
        return false; // 如果未找到目标值，返回 false
    }

    /**
     * 主方法，处理输入并输出结果。
     * 该方法从标准输入读取矩阵和目标值，并输出目标值是否存在于矩阵中。
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建扫描器对象
        int m = sc.nextInt(); // 读取矩阵的行数
        int n = sc.nextInt(); // 读取矩阵的列数
        sc.nextLine(); // 读取换行符
        int[][] matrix = new int[m][n]; // 创建矩阵
        for(int i = 0; i < m; i++) {
            String[] line = sc.nextLine().split(","); // 读取每一行
            for(int j = 0; j < line.length; j++) {
                matrix[i][j] = Integer.parseInt(line[j]); // 解析矩阵元素
            }
        }
        int target = sc.nextInt(); // 读取目标值
        searchMatrix2 sm = new searchMatrix2(); // 创建对象
        System.out.println(sm.searchMat(matrix, target)); // 输出目标值是否存在于矩阵中
        sc.close(); // 关闭扫描器
    }
}
